package _interview100;

import java.util.Arrays;

/**
 * 70. 爬楼梯
 */
public class No70 {
    private int[] cache;

    public int climbStairs(int n) {
        cache = new int[n];
        Arrays.fill(cache, -1);
        return dfs(n - 1) + dfs(n - 2);
    }

    private int dfs(int i) {
        if (i < 0) return 0;
        else if (cache[i] != -1) return cache[i];
        else if (i == 0) return cache[i] = 1;
        else return cache[i] = dfs(i - 1) + dfs(i - 2);
    }
}
